﻿#define _CRT_SECURE_NO_WARNINGS
  
//力扣141 带环链表

//判断链表是否带环
//如果链表有环，获取环的入口点

//1.给你一个链表的头节点 head ，判断链表中是否有环。

//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
//为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
//注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
//如果链表中存在环 ，则返回 true 。 否则，返回 false 。

//思路：利用快慢指针
//(1)f/*-+st走到环里了，slow或许还没有走到环，至到fast追上slow，那就是有环。
//(2)fast能走到NULL，那就说明没有环。

/*
bool hasCycle(struct ListNode* head) {
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)      //链表可能是奇数个fast->next为NULL结束，也可能是偶数个fast为NULL结束，
    {
        slow = slow->next;
        fast = fast->next->next;    //slow一次走一步， fast一次走两步

        if (slow == fast)           // fast追上slow了。
            return true;
    }
              
    return false;                   //如果fast && fast->next一直不为NULL，那就是有环，否则就是无环
}

*/


//2.给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
//为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
//如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

//结论是：一个指针从head头开始走，另一个指针从meet(fast与slow相遇的结点)开始走，他们会在环的入口点相遇。
//L = (N - 1) * C + (C - X) 这个公式推导出来的

//证明思路
//1.假设入环前的距离是L，假设环的大小是C， 假设slow在与fast相遇之前，走了X，
//那么slow走的路程就是L + X。
// 
//fast走的路程是L + C + X，这个距离这么算是不对的，环大点可以这么算，
//但是当环很小的时候，比较是2, slow走一步，fast在环里就走了一圈，slow走一步，fast在环里就走了一圈，
//那L + C + X这个距离就不对了。
//环比较大，fast可能就走了一圈，
//环很小的话，fast可能就走了很多圈。
//所以还得假设下
// 
//2.假设slow进环前，fast在环里转了N圈。N >= 1，所以fast走的路程是L + N * C + X;
//3.又因为fast走的路程是slow路程的2倍
//所以
// L + N * C + X = 2(L + X)
// N * C = L + X
// L = N * C - X
// L = (N - 1) * C + (C - X)
//从meet开始走，走(N - 1) * C, 不管走多少圈，meet还是meet，
//然后再走C - X
//其实就相当于meet走了C - X，一圈一圈的，位置都没有变，C - X = L

//解题思路
//先判断是否有环，有环的话，找到meet
//当meet==head的时候，那就是环的入口点。

/*
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast, * slow;
    fast = slow = head;
    while (fast && fast->next)      //链表可能是奇数个fast->next为NULL结束，也可能是偶数个fast为NULL结束，
    {
        slow = slow->next;
        fast = fast->next->next;    //slow一次走一步， fast一次走两步

        if (slow == fast)           // fast追上slow了。
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }

    return NULL;
}
*/

//链表求环入口的问题还可以转换为两个链表的相交问题

//把meet的下一个结点设置为newhead， 把meet->next置为NULL。 相当于把环断开了
//现在再求环的入口，就相当于是求head链表和newhead链表，相交的第一个交点的问题。
